package com.datastructure.hashtable;

public class HashTable {
    //该数组存放学生链表
    private StuLinkedList[] stuLinkedList;
    //数组大小，也是哈希表大小
    private int size;

    HashTable(int size){
        this.size = size;
        stuLinkedList = new StuLinkedList[size];
        //对数组中每一个链表进行初始化
        for (int i=0; i<size; ++i) {
            stuLinkedList[i] = new StuLinkedList();
        }
    }

    //向哈希表中添加元素
    public void add(String name, int id) {
        //通过散列函数计算在数组中的位置
        int stuLinkedNum = hashFun(id);
        //将元素添加到对应位置的链表中
        stuLinkedList[stuLinkedNum].add(name, id);
    }

    //在哈希表中查找元素
    public Stu findStuById(int id) {
        //通过散列函数计算在数组中的位置
        int stuLinkedNum = hashFun(id);
        //在对应位置的链表中查找元素
        Stu stu = stuLinkedList[stuLinkedNum].findStuById(id);
        System.out.printf("id 为 %d 的学生", id);
        if (stu == null) {
            System.out.println("没有找到");
            return null;
        } else {
            System.out.printf("姓名为 %s", stu.name);
            return stu;
        }
    }

    public void show() {
        for(int i=0; i<size; ++i) {
            System.out.print("下标 " + i +", ");
            stuLinkedList[i].show();
        }
        System.out.println();
    }

    //哈希函数
    private int hashFun(int id) {
        return id % size;
    }
}

class StuLinkedList {
    //头指针，指向第一个 Student
    private Stu head;
    StuLinkedList() {
        this.head = null;
    }
    //向链表中添加元素
    public void add(String name, int id) {
        if(head == null) {
            head = new Stu(name, id);
            return;
        }
        Stu curStu = head;
        while (curStu.next != null) {
            curStu = curStu.next;
        }
        curStu.next = new Stu(name, id);
    }

    //在链表中查找元素
    public Stu findStuById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        //遍历链表
        Stu curStu = head;
        while (curStu != null) {
            if (curStu.id == id) {
                return curStu;
            }
            curStu = curStu.next;
        }
        return null;
    }

    public void show() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        System.out.print("链表信息为：");
        Stu curStu = head;
        while (curStu != null) {
            System.out.printf("id = %d, name = %s ;\t", curStu.id, curStu.name);
            curStu = curStu.next;
        }
        System.out.println();
    }

}

//定义学生节点
class Stu {
    //学生姓名
    String name;
    //学生 id
    int id;
    Stu next;

    Stu() {
        this.name = null;
        this.id = id;
        this.next = null;
    }
    Stu(String name, int id) {
        this.name = name;
        this.id = id;
        this.next = null;
    }
}
